home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_300 / 332_02 / stone.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-03-28  |  27.9 KB  |  1,058 lines
  1. /*----------------------------------------------------*- Fundamental -*-
  2.  
  3. Facility:        stone(6)
  4.  
  5. File:            stone.c
  6.  
  7. Associated files:    - (none)
  8.  
  9. Description:        Plays the game of Kalah.
  10.  
  11. Notes:            This program was originally available in two
  12.             versions, one for dumb terminals and ttys
  13.             (stone) and one for H19-type terminals
  14.             (hstone).  The present version is a cleaned-
  15.             up implementation of hstone, adapted for a
  16.             curses-compatible terminal interface.
  17.  
  18.             The program will only work on terminals with
  19.             at least 80 chars per line, and with at least
  20.             24 lines.  The only reason for this limit
  21.             is the screen layout - see printb()
  22.  
  23. Portability:        Edited to conform to X/Open Portability
  24.             Guide, ed. 3
  25.  
  26. Authors:        Terry Hayes & Clark Baker
  27.             Real-Time Systems Group
  28.             MIT Lab for Computer Science
  29.  
  30. Editor:            Leor Zolman
  31.  
  32.             Anders Thulin
  33.             Rydsvagen 288
  34.             S-582 50 Linkoping
  35.             SWEDEN
  36.  
  37. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 
  38.  
  39. Edit history :
  40.  
  41. Vers  Ed   Date           By               Comments
  42. ----  ---  ----------  ----------------  -------------------------------
  43.  1.0    0  19xx-xx-xx  Hayes & Baker
  44.  1.1    1  19xx-xx-xx  Leor Zolman
  45.  1.2    2  1990-03-25  Anders Thulin
  46.  
  47. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  48.  
  49. /*---  Configuration options:  ----------------------------------------
  50.  
  51. System configuration options:
  52. =============================
  53.  
  54.   ANSI        ANSI C
  55.   BSD        BSD Unix, SunOS 3.5
  56.   SV2        AT&T UNIX System V.2
  57.   XPG3        X/Open Portability Guide, ed. 3
  58.  
  59. If you have an ANSI C conformant compiler, define ANSI.  If not, choose
  60. the definition that most closely matches your environment.
  61.  
  62.  
  63. Program configuration options:
  64. ==============================
  65.  
  66.   TRACE        This definition should not be changed. It is used to
  67.         remove all code that in the original version wrote
  68.         tracing information to the screen. As these completely
  69.         destroy the screen layout they have been removed.
  70.  
  71.         A good way of including them in the program would be to
  72.         change them to write to a special trace window. This is
  73.         left as an exercise for the reader.
  74.  
  75.   BEEP        See 'comments' below
  76.  
  77.   FUDGE (65)    Used to determine the total number of game tree nodes
  78.         (game positions) to be examined -- computed as
  79.  
  80.           FUDGE * chosen level of difficulty
  81.  
  82.   MAX_LEVEL (1000)
  83.  
  84.         The maximum level of difficulty allowed. FUDGE * MAX_LEVEL
  85.         should not be larger than INT_MAX.
  86.  
  87. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  88.  
  89. #define    ANSI    1
  90. #define    BSD    0
  91. #define    SV2    0
  92. #define    XPG3    0
  93.  
  94. #define    TRACE    0    
  95. #define    BEEP()        beep()
  96.  
  97. #define    FUDGE        32
  98. #define    MAX_LEVEL    1000
  99.  
  100. /* - - end of configuration options - - - - - - - - - - - - - - - - - - - */
  101.  
  102. #if ANSI
  103. # include <ctype.h>
  104. # include <curses.h>
  105. # include <stdio.h>
  106. # include <stdlib.h>
  107.  extern int getopt(int argc, char *argv[], char optstring[]);
  108.  extern int optind;
  109. #endif
  110.  
  111. #if BSD
  112. # include <ctype.h>
  113. # include <curses.h>
  114. # include <stdio.h>
  115.  extern int getopt();
  116.  extern int optind;
  117. #endif
  118.  
  119. #if SV2
  120. # include <ctype.h>
  121. # include <curses.h>
  122. # include <stdio.h>
  123.  extern int getopt();
  124.  extern int optind;
  125. #endif
  126.  
  127. #if XPG3
  128. # include <ctype.h>
  129. # include <curses.h>
  130. # include <stdio.h>
  131. # include <stdlib.h>
  132.  extern int getopt();
  133.  extern int optind;
  134. #endif
  135.  
  136. /*--- Comments on known problems: ------------------------------------------
  137.  
  138. curses
  139.  
  140.   Some older implementation of curses does not have the beep()
  141.   function, which beeps at the user.
  142.  
  143.   On such systems, you may need to define BEEP to produce a
  144.   beep in some other way, like fputc(0x07, stderr).
  145.  
  146.   If you cannot beep at all, try to flash the screen.
  147.  
  148.   If you cannot do either, just define BEEP to be empty, which is
  149.   permitted behaviour for curses' beep().
  150.  
  151. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -*/
  152.  
  153. /*--- Original notes on the program:  -----------------------------------
  154.  
  155. "STONE"
  156. (otherwise known as "Awari")
  157.  
  158. This version written by
  159.     Terry Hayes & Clark Baker
  160.     Real-Time Systems Group
  161.     MIT Lab for Computer Science
  162. (and hacked up a little by Leor Zolman)
  163.  
  164. The algorithm used for STONE is a common one to Artificial Intelligence
  165. people: the "Alpha-Beta" pruning heuristic. By searching up and down a tree
  166. of possible moves and keeping record of the minimum and maximum scores from
  167. the terminal static evaluations, it becomes possible to pinpoint move
  168. variations which can in no way affect the outcome of the search.  Thus,
  169. those variations can be simply discarded, saving expensive static evaluation
  170. time. 
  171.  
  172. #if TRACE
  173.  
  174. To have the program print out some search statistics for every move
  175. evaluation, type the command as
  176.  
  177.   A> stone -d
  178.  
  179. To also see a move-by-move trace of each terminal evaluation, type
  180.  
  181.   A> stones -a
  182.  
  183. #end 
  184.  
  185. THIS is the kind of program that lets C show its stuff; Powerful expression
  186. operators and recursion combine to let a powerful algorithm be implemented
  187. painlessly. 
  188.  
  189. And it's fun to play!
  190.  
  191. Rules of the game:
  192.  
  193. Each player has six pits in front of him and a "home" pit on one side (the
  194. computer's home pit is on the left; your home pit is on the right.)
  195.  
  196. At the start of the game, all pits except the home pits are filled with n
  197. stones, where n can be anything from 1 to 6. 
  198.  
  199. To make a move, a player picks one of the six pits on his side of the board
  200. that has stones in it, and redistributes the stones one-by-one going
  201. counter-clockwise around the board, starting with the pit following the one
  202. picked.  The opponent's HOME pit is never deposited into. 
  203.  
  204. If the LAST stone happens to fall in that player's home pit, he moves again. 
  205.  
  206. If the LAST stone falls into an empty pit on the moving player's side of
  207. board, then any stones in the pit OPPOSITE to that go into the moving
  208. player's home pit. 
  209.  
  210. When either player clears the six pits on his side of the board, the game is
  211. over.  The other player takes all stones in his six pits and places them in
  212. his home pit.  Then, the player with the most stones in his home pit is the
  213. winner. 
  214.  
  215. The six pits on the human side are numbered one to six from left to right;
  216. the six pits on the computer's side are numbered one to six right-to-left. 
  217.  
  218. The standard game seems to be with three stones; less stones make it
  219. somewhat easier (for both you AND the computer), while more stones
  220. complicate the game.  As far as difficulty goes, well...it USED to be on a
  221. scale of 1 to 50, but I couldn't win it at level 1.  So I changed it to
  222. 1-300, and couldn't win at level 1.  So I changed it to 1-1000, and if I
  223. STILL can't win it at level 1, I think I'm gonna commit suicide. 
  224.  
  225. Good Luck!!!
  226.  
  227. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
  228.  
  229. Notes added by Anders Thulin:
  230.  
  231. The present program plays the game of Kalah.  It does not play the game of
  232. Oware, which has slightly more complicated rules.  For a description of
  233. Oware (as well as other games of the Mancala family), take a look at Ian
  234. Lennox-Smith's series of articles in the British magazine Games & Puzzles,
  235. no. 26-29 (July-October 1974), or any reliable book on board games (there
  236. *are* unreliable ones!)
  237.  
  238. Kalah is usually played with 3-6 stones in each pit. The game with only one
  239. stone in each pit is 'trivial' (won by the first player), as well as that
  240. with two stones. It is reasonably easy to modify this program to check this
  241. statement out. 
  242.  
  243. There is an interesting paper on a learning implementation of Kalah in
  244. Machine Intelligence vol. 3, ed. D. Michie, Edinburgh 1974. The paper is
  245. written by A. G. Bell; the title is 'Kalah on Atlas'.
  246.  
  247. For a description of the alpha-beta pruning algorithm, see almost any
  248. introductory work on artificial intelligence. A good description is given by
  249. David Levy in The Chess Computer Handbook, Batsford, London 1984.
  250.  
  251. For an interesting description of different minimax algorithms (including
  252. the alpha-beta algorithm) see the article 'A Comparison of Minimax Tree
  253. Search Algorithms' by Murray S. Campbell and T.A. Marsland in the journal
  254. Artificial Intelligence, vol. 20 (1983), p. 347-367. This paper describes a
  255. slightly 'better' alpha-beta algorithm, compared to that used in this
  256. program.
  257.  
  258. Finally, the author of the original comments makes a peculiar statement in
  259. his last lines in regard to the difficulty level of the program.
  260.  
  261. Changing the maximum difficulty level from 50, to 300, to 1000 does not
  262. change the level of play on level 1. It only changes the size of the game
  263. tree that is being examined.  The level number corresponds to the number of
  264. positions (nodes) that should be examined.  Playing at level 1 always gives
  265. the same performance, regardless of the maximum number of levels.
  266.  
  267. However, if you find that level 1 is too difficult, change the FUDGE
  268. parameter above; it is used to determine the final number of nodes.  A FUDGE
  269. factor of 1 (or even 0) makes for the easiest play.
  270.  
  271. I do really hope that he did discover this in time ...
  272.  
  273. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
  274.  
  275. #define    NR_PITS        6    
  276. #define    BOARD_SIZE    (2*(NR_PITS+1))
  277.  
  278. #ifndef TRUE            /* should be defined in <curses.h> */
  279. # define  TRUE        1
  280. # define  FALSE        0
  281. #endif
  282.  
  283. #define    MAX(i, j)    ((i) > (j) ? (i) : (j))
  284. #define    MIN(i, j)    ((i) < (j) ? (i) : (j))
  285.  
  286. #define    P_FIRST        1            /* Player's first pit    */
  287. #define    P_KALAH        (P_FIRST+NR_PITS)    /* Player's kalah    */
  288. #define    C_FIRST        (P_KALAH+1)        /* Computer's first pit    */
  289. #define    C_KALAH        0            /* Computer's kalah    */
  290.  
  291. typedef    char t_board[BOARD_SIZE];
  292.  
  293. /*----------------------------------------------------------------------
  294.   Local variables:
  295. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  296.  
  297. int     DEPTH;        /* The current depth of the playing tree     */
  298. int     MAXDEPTH;    /* The max depth reached during evaluation    */
  299. unsigned CALLS;        /* ??? Same as WIDTH ???            */
  300. unsigned TOTDEPTH;    /* ... */
  301. unsigned WIDTH;        /* Total number of nodes evaluated        */
  302. unsigned TERM;        /* ... */
  303. unsigned COUNT;        /* The max number of nodes to be examined    */
  304. int      NUM;        /* Nr of stones per pit at beginning of game    */
  305.  
  306. int    pbegins;    /* true if player moves first    */
  307.  
  308. unsigned total;        /* nr of moves actually considered        */
  309.  
  310. #if TRACE
  311. /*  Command line options:    */
  312.  
  313. int      ab;        /* TRUE if printouts of ... */
  314. int     db;        /* TRUE if printouts of ... */
  315.  
  316. #endif /* TRACE */
  317.  
  318. /*----------------------------------------------------------------------
  319.   Local routines:
  320. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  321.  
  322. #if __STDC__ != 0
  323.  static int  comp(char *board);
  324.  static int  comp1(char *board, int who, unsigned count, int alpha, int beta); 
  325.  static int  countnodes(char *board, int start); 
  326.  static int  dmove(char *new, int move);
  327.  static int  done(char *board);
  328.  static void get_game_parameters(void);
  329.  static int  get_players_move(char *board);
  330.  static void initb(t_board board);
  331.  static int  mmove(char *old, char *new, int mov);
  332.  static int  mod(int i, int j);
  333.  static void printb(t_board board);
  334. #else
  335.  static int  comp();
  336.  static int  comp1(); 
  337.  static int  countnodes(); 
  338.  static int  dmove();
  339.  static int  done();
  340.  static void get_game_parameters();
  341.  static int  get_players_move();
  342.  static void initb();
  343.  static int  mmove();
  344.  static int  mod();
  345.  static void printb();
  346. #endif
  347.  
  348. /*----------------------------------------------------------------------
  349.  
  350. Routine:    dmove
  351.  
  352. Description:    Perform a move and print out the resulting board.
  353.         Return TRUE or FALSE depending on whether the
  354.         move was a continuation move or not (see mmove)
  355.  
  356. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  357.  
  358. static int dmove(new, mov)
  359. char *new;
  360. int   mov;
  361. {
  362.   int i;
  363.   i = mmove(new,new,mov);
  364.   printb(new);
  365.   return(i);
  366. }
  367.  
  368. /*----------------------------------------------------------------------
  369.  
  370. Routine:    done
  371.  
  372. Description:    Returns TRUE if any side is out of stones
  373.  
  374. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  375.  
  376. static int done(board)
  377. char *board;
  378. {
  379.   int c_stones;        /* Stones in computer's pits     */
  380.   int p_stones;        /* Stones in player's pits    */
  381.   int i;
  382.  
  383.   c_stones = p_stones = 0;
  384.  
  385.   for (i=0; i<NR_PITS; i++) {
  386.     p_stones += board[P_FIRST+i];
  387.     c_stones += board[C_FIRST+i];
  388.   }
  389.  
  390.   return (p_stones == 0) || (c_stones == 0);
  391. }
  392.  
  393. /*----------------------------------------------------------------------
  394.  
  395. Routine:    get_game_parameters
  396.  
  397. Description:    ask user for various param values
  398.  
  399. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  400.  
  401. static void get_game_parameters()
  402. {
  403.   char string[80];
  404.   int  i;
  405.  
  406.   i = 17;
  407.   while (i < LINES) {
  408.     move(i, 0); clrtoeol();
  409.     i++;
  410.   }
  411.  
  412.   /*  1.  Choose difficulty level:    */
  413.  
  414.   do {
  415.     move(18, 0); printw("Enter difficulty level (1-%d): ", MAX_LEVEL);
  416.     clrtoeol(); refresh();
  417.     if ( getstr(string) == ERR) {
  418.       printw("Error: getstr() returns error\n");  
  419.     }
  420.     i = atoi(string);
  421.     if (i<1 || i>MAX_LEVEL) {
  422.       printw("Error: level %d is out of range!\n", i);
  423.     }
  424.   } while (i<1 || i>MAX_LEVEL);;
  425.  
  426.   COUNT = i * FUDGE;
  427.  
  428.   /*  2.  Choose number of stones:    */
  429.  
  430.   do {
  431.     move(19, 0); addstr("Number of stones : "); clrtoeol();
  432.     refresh();
  433.     if (getstr(string) == ERR) {
  434.       printw("Error: getstr() returns ERR\n");
  435.     }
  436.     i = atoi(string);
  437.     if (i < 1) {
  438.       printw("Error: can't play with %d stones!\n", i);
  439.     }
  440.   } while (i < 1);;
  441.   NUM = i;
  442.  
  443.   /*  3.  Choose who's first to move:    */
  444.  
  445.   do {
  446.     move(20, 0); addstr("Do you want to go first (y or n)? "); clrtoeol();
  447.     refresh();
  448.     getstr(string);
  449.     i = toupper(string[0]);
  450.     if (i != 'Y' && i != 'N') {
  451.       addstr("Please input 'y' or 'n'!\n");
  452.     }
  453.   } while (i != 'Y' && i != 'N');
  454.   pbegins = (i == 'Y');
  455.  
  456.   /*  4.  Remove the questions:  */
  457.  
  458.   move(18, 0); clrtoeol();
  459.   move(19, 0); clrtoeol();
  460.   move(20, 0); clrtoeol(); 
  461. }
  462.  
  463. /*----------------------------------------------------------------------
  464.  
  465. Routine:    get_players_move
  466.  
  467. Description:    requests a legal move from the user, and returns
  468.         it as function value.
  469.  
  470.         legal moves for the user is in the range 
  471.         1..NR_PITS.
  472.  
  473.         If the user enters a 'q' the special move -1
  474.         is returned.
  475.  
  476. Problems:    The atoi() routine does not set errno on all systems.
  477.  
  478. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  479.  
  480. static int get_players_move(board)
  481. char *board;
  482. {
  483.   char  string[80];
  484.   int    p_move;
  485.  
  486.   p_move = 0;
  487.   while (p_move == 0) {
  488.     move(20, 0); addstr("Your move: "); clrtoeol();
  489.     refresh();
  490.     getstr(string);
  491.     if (toupper(string[0]) == 'Q') {
  492.       p_move = -1;
  493.     } else {
  494.       p_move = atoi(string);
  495.       if (p_move < 1 || p_move > NR_PITS || board[p_move] == 0) {
  496.         addstr("Illegal!!"); BEEP();
  497.         p_move = 0;
  498.       }
  499.     }
  500.   }
  501.   move(21, 0); clrtoeol();    /* remove any remaining 'Illegal!' lines */
  502.  
  503.   return p_move;
  504. }
  505.  
  506. /*----------------------------------------------------------------------
  507.  
  508. Routine:    main
  509.  
  510. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -  */
  511.  
  512. int main(argc,argv)
  513. int   argc;
  514. char *argv[];
  515. {
  516.   int    pmove;        /* player's latest move        */
  517.   int    cmove;        /* computer's latest move    */
  518.  
  519.   int    hum;        /* user's score        */
  520.   int    com;        /* program's score    */
  521.  
  522.   t_board board;    /* game board        */
  523.  
  524.   int    i;        /* scratch variables    */
  525.   int    errflag;
  526.   int    c;
  527.   char    string[100];
  528.  
  529. #if TRACE
  530.   char  *optchars = "ab";
  531. #else
  532.   char  *optchars = "";
  533. #endif
  534.  
  535.   /*  1.  Get command line arguments:        */
  536.  
  537. #if TRACE
  538.   ab = db = 0;
  539. #endif
  540.   errflag = 0;
  541.  
  542.   while ((c  = getopt(argc, argv, optchars)) != EOF) {
  543.     switch (c) {
  544.       default :
  545.         fprintf(stderr, "stone(main): error in getopt()");
  546.         exit(1);
  547.  
  548.       case '?' :    /* getopt() found illegal option letter */
  549.         errflag = TRUE;
  550.       break;        /* has already complained        */
  551.  
  552. #if TRACE
  553.       case 'a' :
  554.     ab = TRUE;
  555.     break;
  556.  
  557.       case 'd' :
  558.     ab = db = TRUE;
  559.     break;
  560. #endif 
  561.     }
  562.   }
  563.  
  564.   if (errflag || optind < argc) { /* error or arguments */
  565. #if TRACE
  566.     fprintf(stderr, "usage: stone [-ad]\n");
  567. #else
  568.     fprintf(stderr, "usage: stone\n");
  569. #endif
  570.     exit(1);    
  571.   }
  572.  
  573.   initscr();
  574.  
  575.   /*  2.  Keep playing as long as user wants to:    */
  576.  
  577.   do {
  578.   
  579.     /*  3.  Display an empty board:  */
  580.  
  581.     initb(board);
  582.     printb(board);
  583.  
  584.     /*  4.  Get game parameters:    */
  585.  
  586.     get_game_parameters();
  587.     initb(board);
  588.  
  589.     if (!pbegins) goto first;
  590.  
  591.     /*  5.  Main move loop:    */
  592.  
  593.     while (!done(board)) {
  594.  
  595.       /*  6.  Get player's move        */
  596.  
  597.       do {
  598.         pmove = get_players_move(board);
  599.         if (pmove == -1) {        /* user entered 'q' */
  600.           goto quit;
  601.         }
  602.       } while (!dmove(board, pmove) && !done(board));
  603.  
  604.       /*  7.  Get computer's move:    */
  605.  
  606. first:
  607.       {
  608.         int first = 0, y, x;
  609.  
  610.         move(20, 0); addstr("I'm thinking..."); clrtoeol();
  611.         while (!done(board)) {
  612.           cmove = comp(board);
  613.  
  614.           if (first == 0) {
  615.             move(19, 0); printw("Computer moves: %d", cmove-(NR_PITS+1));
  616.               clrtoeol();
  617.             getyx(stdscr, y, x);
  618.             first++;
  619.           } else {
  620.             move(y, x);
  621.             printw(", %d", cmove-(NR_PITS+1));
  622.             getyx(stdscr, y, x);
  623.           }
  624.           
  625.           if (dmove(board, cmove)) {
  626.             move(20, 0); clrtoeol();    /* Not thinking anymore */
  627.             break;
  628.           }
  629.         }
  630.       }
  631.  
  632.     } /* end of main move loop */
  633.  
  634.     /*  8.  Game is over. Sum up the results:    */
  635.  
  636.     com = board[C_KALAH]; 
  637.     hum = board[P_KALAH];
  638.     for (i = 1; i <= NR_PITS; i++) { 
  639.       hum += board[i];
  640.       com += board[NR_PITS+1+i];
  641.     }
  642.  
  643.     move(22, 0); printw("Score:   me %d  you %d . . . ", com, hum);
  644.     if (com > hum) {
  645.       addstr("I win\n");
  646.     }
  647.     else if (com == hum) {
  648.       addstr("game is a draw\n");
  649.     } else {
  650.       addstr("you win\n");
  651.     }
  652.  
  653. quit:
  654.     move(23, 0); addstr("New game (y or n): "); clrtoeol();
  655.     refresh();
  656.     getstr(string);
  657.  
  658.   } while (toupper(string[0]) == 'Y');
  659.  
  660.   endwin();  
  661.  
  662.   return 0;
  663. }
  664.  
  665. /*----------------------------------------------------------------------
  666.  
  667. Routine:    mmove
  668.  
  669. Description:    Perform the move 'move' on the 'old' board, and
  670.         put the new board in 'new'. 
  671.  
  672.         Return FALSE only if the move ended in a kalah.
  673.         This indicates that the mover may move again.
  674.         Return TRUE otherwise.
  675.  
  676. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  677.  
  678. static int mmove(old, new, mov)
  679. char *old; 
  680. char *new;
  681. int   mov;
  682. {
  683.   int i; 
  684.   int who;
  685.  
  686.   /*  1.  Check that 'move' is legal on 'old':    */
  687.  
  688.   if ( (mov < P_FIRST) || (mov == P_KALAH) ||
  689.        (mov >= BOARD_SIZE)      ||
  690.        old[mov] == 0) {
  691.     printf("Bad arg to mmove: %d",mov);
  692.   }
  693.  
  694.   /*  2.  Do some setting up:    */
  695.  
  696.   total++;    /* Total number of moves made during tree search */
  697.  
  698.   for (i = 0; i < BOARD_SIZE; ++i) {
  699.     new[i] = old[i];
  700.   }
  701.  
  702.   who = (mov < P_KALAH ? 1 : 0);  /* 1 == player, 0 == computer */
  703.  
  704.   /*  3.  Make move:    */
  705.  
  706.   i = old[mov];    /* 'i' is the stones 'in hand' */
  707.   new[mov] = 0;
  708.  
  709.   while (i--) {
  710.     mov = mod(mov, who);
  711.     ++new[mov];
  712.   }
  713.  
  714.   /*  3.  Did we make a capture? */
  715.  
  716.   if (new[mov] == 1 && who == (mov < 7 ? 1 : 0) && mov && mov != 7) {
  717.     new[who*P_KALAH] += new[14-mov];
  718.     new[14-mov] = 0;
  719.   }
  720.  
  721.   /*  4.  Did the move end in a kalah? */
  722.  
  723.   return (!(mov == C_KALAH || mov == P_KALAH));
  724.  
  725. }
  726.  
  727. /*----------------------------------------------------------------------
  728.  
  729. Routine:    mod
  730.  
  731. Description:    Return the number of the pit after 'i'.
  732.  
  733. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  734.  
  735. static int mod(i, player)
  736. int i,player;
  737. {
  738.   /*  1.  Get next pit number: */
  739.  
  740.   ++i;
  741.  
  742.   /*  2.  Only player may use player's own kalah:    */
  743.  
  744.   if (i == P_KALAH) return( player ? P_KALAH : P_KALAH+1);
  745.   if (i >= BOARD_SIZE) return ( player ? P_FIRST : C_KALAH);
  746.  
  747.   return(i);
  748. }
  749.  
  750. /*----------------------------------------------------------------------
  751.  
  752. Routine:    initb
  753.  
  754. Description:    Initialize the board to starting position
  755.  
  756. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  757.  
  758. static void initb(board)
  759. t_board board;
  760. {
  761.   int i;
  762.  
  763.   for (i=0; i<BOARD_SIZE; i++) {
  764.     board[i] = NUM;
  765.   }
  766.   board[P_KALAH] = board[C_KALAH] = 0;
  767.   printb(board);
  768. }
  769.  
  770. /*----------------------------------------------------------------------
  771.  
  772. Routine:    printb
  773.  
  774. Description:    Display the kalah board on the screen.
  775.  
  776.         The board is displayed in lines 0-16,
  777.         columns 0-77.
  778.  
  779. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  780.  
  781. static char screen[17][78+1] = { /* Remember trailing \0! */
  782. "+----------------------------------------------------------------------------+",
  783. "|                                                                            |",
  784. "|       ME        6       5       4       3       2       1                  |",
  785. "|              +-----+ +-----+ +-----+ +-----+ +-----+ +-----+               |",
  786. "|              |     | |     | |     | |     | |     | |     |               |",
  787. "|              |     | |     | |     | |     | |     | |     |               |",
  788. "|              |     | |     | |     | |     | |     | |     |               |",
  789. "|              +-----+ +-----+ +-----+ +-----+ +-----+ +-----+               |",
  790. "|                                                                            |",
  791. "|              +-----+ +-----+ +-----+ +-----+ +-----+ +-----+               |",
  792. "|              |     | |     | |     | |     | |     | |     |               |",
  793. "|              |     | |     | |     | |     | |     | |     |               |",
  794. "|              |     | |     | |     | |     | |     | |     |               |",
  795. "|              +-----+ +-----+ +-----+ +-----+ +-----+ +-----+               |",
  796. "|                 1       2       3       4       5       6        YOU       |",
  797. "|                                                                            |",
  798. "+----------------------------------------------------------------------------+"
  799. };
  800.  
  801. /* 'centres' of the 0-13 pits */
  802.  
  803. static int ypos[14] = { 5, 11, 11, 11, 11, 11, 11, 11,  5,  5,  5,  5,  5,  5};
  804. static int xpos[14] = { 8, 17, 25, 33, 41, 49, 57, 65, 57, 49, 41, 33, 25, 17};
  805.  
  806. static void printb(board)
  807. t_board board;
  808. {
  809.   int i;
  810.  
  811.   /*  1.  Print empty board layout:  */
  812.  
  813.   for (i=0; i<17; i++) {
  814.     move(i,0);
  815.     addstr(screen[i]);
  816.   }
  817.   
  818.   /*  2.  Fill in pit contents:  */
  819.  
  820.   for (i=0; i<BOARD_SIZE; i++) {
  821.     move(ypos[i], xpos[i]);
  822.     printw("%3d", board[i]);
  823.   }
  824.  
  825.   /*  3.  Update board:  */
  826.  
  827.   refresh();
  828. }
  829.  
  830. /*----------------------------------------------------------------------
  831.  
  832. Routine:    comp
  833.  
  834. Description:    given the board 'board', calulate the best
  835.         next move and return it as result.
  836.  
  837. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  838.  
  839. static int comp(board)
  840. char *board;
  841. {
  842.   int score;
  843.   int bestscore,best;
  844.   char temp[14];
  845.   int i;
  846.   unsigned nodes;
  847.  
  848.   DEPTH = MAXDEPTH = CALLS = TOTDEPTH = WIDTH = TERM = 0;
  849.   total = 0;
  850.  
  851.   /*  1. Only one possible move? Then select that:    */
  852.  
  853.   if ((i = countnodes(board, C_FIRST)) == 1) {
  854.     for (best = C_FIRST; best < C_FIRST+NR_PITS-1; ++best) {
  855.       if (board[best]) {
  856.         return(best);
  857.       }
  858.     }
  859.   }
  860.  
  861. #if 0    /* DEBUG only */
  862.   if (i < 1) {
  863.     printw("ABORT! comp entered when no moves possible!");
  864.     exit(1);
  865.   }
  866. #endif
  867.  
  868.   /*  2. Try each move that is left. Select the best one:    */
  869.  
  870.   nodes = COUNT/i;
  871.   bestscore = -10000;        /* should be MIN_INT */
  872.   for (i = 13; i > P_KALAH; --i) {
  873.     if (board[i]) {
  874.       score = mmove(board,temp,i);
  875. #if !TRACE
  876.       score = comp1(temp, score, nodes, bestscore, 10000);
  877. #else
  878.       score = comp1(temp, score, nodes, db? -10000 : bestscore, 10000);
  879.       if (db > 0) {
  880.         printf("MOVE: %2d SCORE: %5d",
  881.                 i-P_KALAH,
  882.              (score>=1000)?(score-1000):
  883.               ((score<= -1000)?(score+1000):score));
  884.     if (score > 1000 || score < -1000) {
  885.           printf("  for SURE");
  886.         }
  887.         printf("\n");
  888.       }
  889. #endif
  890.       if (score > bestscore) {
  891.         bestscore = score;
  892.         best = i;
  893.       }
  894.     }
  895.   }
  896.  
  897.  /* - -
  898.  
  899. Indicate if we think we're winning or losing.
  900.  
  901. Comment by A. Thulin:
  902.  
  903. The program is sometimes wrong, altough it often is difficult to refute it,
  904. especially with many stones.  The best strategy for the player to win a game
  905. that the program thinks it has won, seems to be to play a 'waiting' game.
  906.  
  907. The fact that the program *is* wrong indicates an error somewhere, but it
  908. does not appear to be an obvious one...
  909.  
  910. - -*/
  911.  
  912.   move(18, 0);
  913.   if (bestscore > 1000) {
  914.     addstr("(I think I've got you!)");
  915.   } else if (bestscore < -1000) {
  916.     addstr("(I think you've got me...)");
  917.   } else {
  918.     clrtoeol();
  919.   }
  920.  
  921. #if TRACE
  922.   if (db) {
  923.     printf("\nCount: %u\n",total);
  924.     printf("Maximum depth: %d\nAverage depth: %u\n", MAXDEPTH,TOTDEPTH/CALLS);
  925.     printf("Terminal Evaluations: %u\nPlayed out: %u\n",WIDTH,TERM);
  926.   }
  927. #endif
  928.  
  929.   return(best);
  930. }
  931.  
  932. /*----------------------------------------------------------------------
  933.  
  934. Routine:    comp1
  935.  
  936. Description:    The real alpha-beta minmax evaluator
  937.  
  938. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  939.  
  940. static int comp1(board, who, count, alpha, beta)
  941. char     *board;    /* current board */
  942. int       who;        /* who is to move */
  943. unsigned  count;     /* max nr of positions to examine */
  944. int       alpha,    /* ... */
  945.           beta;        /* ... */
  946. {
  947.   int i;
  948.   int turn,new;
  949.   char temp[14];
  950.   unsigned nodes;
  951.  
  952.   ++DEPTH;
  953.   MAXDEPTH = MAX(MAXDEPTH,DEPTH); 
  954.  
  955.   /*  1.  If no nodes left, evaluate position statically:    */
  956.  
  957.   if (count < 1) {        /* No remaining nodes ... */
  958.     ++CALLS;
  959.     TOTDEPTH += DEPTH;
  960.     ++WIDTH;
  961.     --DEPTH;
  962.  
  963.     new = board[C_KALAH]-board[P_KALAH];    
  964.     for (i = 1; i < P_KALAH; ++i) {
  965.       turn = MIN(P_KALAH-i,board[i]);
  966.       new -= 2*turn - board[i];
  967.     }
  968.     for (i = P_KALAH+1; i < 14; ++i) {
  969.       turn = MAX(14-i,board[i]);
  970.       new += 2*turn - board[i];
  971.     }
  972.     if (board[C_KALAH] > 6*NUM) {
  973.       return new+1000;
  974.     }
  975.     if (board[P_KALAH] > 6*NUM) {
  976.       return new-1000;
  977.     }
  978.     return(new);
  979.   }
  980.  
  981.   /*  2.  No more moves to be examined?        */
  982.  
  983.   if (done(board)) {
  984.     ++CALLS;
  985.     TOTDEPTH += DEPTH;
  986.     ++TERM;
  987.     --DEPTH;
  988.  
  989.     new = board[0]+board[8]+board[9]+board[10]+board[11]+board[12]+board[13]
  990.          -board[1]-board[2]-board[3]-board[4]-board[5]-board[6]-board[7];
  991.     if (new < 0) new -= 1000;
  992.     if (new > 0) new += 1000;
  993.     return(new);
  994.   }
  995.  
  996.   /*  3.  Check moves further down in tree:    */
  997.  
  998. #if 0  /* DEBUG printout only */
  999.   if (countnodes(board, 8-who*7) == 0) {
  1000.     printf("BREAKOFF: EMPTY BOARD! who = %d\n", who);
  1001.     printf("done(board) = %d\n", done(board));
  1002.     for (i=0; i<BOARD_SIZE; i++) {
  1003.       printf("%4d", board[i]);
  1004.     }
  1005.     exit(1);
  1006.   }
  1007. #endif
  1008.  
  1009.   nodes = count/countnodes(board,8-who*7);
  1010.   for (i = 7*(1-who)+6; i > 7*(1-who); --i)
  1011.     if (board[i]) {
  1012.       turn = mmove(board,temp,i);
  1013.       new = comp1(temp,(turn ? 1-who : who),nodes,alpha,beta);
  1014. #if TRACE
  1015.       if (ab) printf("DEPTH: %2d  MOVE: %2d  NEW: %4d  ALPHA: %6d  BETA: %6d\n",DEPTH,i,new,alpha,beta);
  1016. #endif
  1017.       if (who) {
  1018.         beta = MIN(new,beta);
  1019.         if (beta <= alpha) {
  1020.           DEPTH--; 
  1021.           return(beta);
  1022.         }
  1023.       }
  1024.       else {
  1025.         alpha = MAX(new,alpha);
  1026.         if (alpha >= beta) {
  1027.           DEPTH--;
  1028.           return(alpha);
  1029.         }
  1030.       }
  1031.     }
  1032.   --DEPTH;
  1033.  
  1034.   return(who ? beta : alpha);
  1035. }
  1036.  
  1037.  
  1038. /*----------------------------------------------------------------------
  1039.  
  1040. Routine:    countnodes
  1041.  
  1042. Description:    How many moves are possible?
  1043.  
  1044. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
  1045.  
  1046. static int countnodes(board, start) 
  1047. int start;
  1048. char *board; 
  1049. {
  1050.   int i, num;
  1051.  
  1052.   num = 0;
  1053.   for (i=start; i < start + NR_PITS; i++)
  1054.     num += (board[i] > 0 ? 1 : 0);
  1055.   return(num);
  1056. }
  1057.  
  1058.